#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn=1e2+10;
int n, q;
int graph[maxn][maxn];
int limit[maxn][maxn];
int dp[maxn][maxn];

int floyd(){
	for(int k=1;k<=n;k++){ // 中间节点
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j]);
			}
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cnt+=dp[i][j];
		}
	}
	return cnt;
	
}

bool check(int x){
	int cnt=x/n; // 进行了几轮
	int rest=x%n; // 剩下几个多进行了一轮
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j]=graph[i][j];
		}
	}
	// 注意这里面每个路径都会被 两端的端点 影响的
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j]-=cnt;
			if(i<=rest){
				dp[i][j]--;
			}
			dp[i][j]=max(dp[i][j], limit[i][j]);
			dp[j][i]=max(dp[i][j], limit[j][i]);
		}
	}
	return floyd()<=q;
}

void solve(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>graph[i][j];
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>limit[i][j];
			dp[i][j]=limit[i][j]; // 先初始化为 最小值
		}
	}
	
	if(floyd()>q) { // 永远不可能满足条件
		cout<<-1<<'\n';
		return ; 
	}
	
	// 开始二分
	int l=-1, r=1e7;
	while (l<r-1) {
		int md=(l+r)/2;
		if(check(md)){
			r=md;
		} else {
			l=md;
		}
	}
	cout<<r<<'\n';
}


signed main(){
	ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);
	solve();
	return 0;
}
